package nachos.threads;

import nachos.machine.*;

import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.ArrayList;

/**
 * A scheduler that chooses threads using a lottery.
 *
 * <p>
 * A lottery scheduler associates a number of tickets with each thread. When a
 * thread needs to be dequeued, a random lottery is held, among all the tickets
 * of all the threads waiting to be dequeued. The thread that holds the winning
 * ticket is chosen.
 *
 * <p>
 * Note that a lottery scheduler must be able to handle a lot of tickets
 * (sometimes billions), so it is not acceptable to maintain state for every
 * ticket.
 *
 * <p>
 * A lottery scheduler must partially solve the priority inversion problem; in
 * particular, tickets must be transferred through locks, and through joins.
 * Unlike a priority scheduler, these tickets add (as opposed to just taking
 * the maximum).
 */
public class LotteryScheduler extends PriorityScheduler {
    
	public static final int priorityMaximum = Integer.MAX_VALUE;  	
    /**
     * Allocate a new lottery scheduler.
     */
    public LotteryScheduler() {
    }
   
     /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState2 getThreadState(KThread thread) {
	if (thread.schedulingState == null)
	    thread.schedulingState = new ThreadState2(thread);

	return (ThreadState2) thread.schedulingState;
    }

    /**
     * Allocate a new lottery thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer tickets from waiting threads
     *					to the owning thread.
     * @return	a new lottery thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
	return new LotteryQueue(transferPriority);
    }


    protected class LotteryQueue extends PriorityScheduler.PriorityQueue {

	    public LotteryQueue(boolean transfer){
		super(transfer);
	    }

	    protected ThreadState pickNextThread(){


		    //Find the maximum priority and waitingTimes for all of the threads that
		    //are waiting for this queue. If priorities are equivalent, checking 
		    //for the oldest time.

		    int ticketAmount = 0;
		    int winner = 0;
		    Random rand = new Random();
		    KThread winnerThread = null;
		    int current = 0;
		    int currentPos = 0;
		    ArrayList ticketList = new ArrayList();
		  
		    if (isEmpty()){
			return null;
		    } 
		    for (int i = 0; i < threadList.size(); i++){
			    KThread thread = (KThread) threadList.get(i);
			    current = getThreadState(thread).getEffectivePriority();
			    ticketList.add(current);
			    ticketAmount += current;
		    }
		    //System.out.println("TicketAmount: " + ticketAmount + "List size: " + threadList.size());
			winner = rand.nextInt(ticketAmount);
			int counter = 0;

         	   //System.out.println("Winner: " + winner);
		   do {
			    currentPos += ((Integer)ticketList.get(counter)).intValue();
			    counter++;
		    } while ( (currentPos < winner));
			
   			counter--;
     		
	   //System.out.println("Thread: " + ((KThread) threadList.get(counter)).getName() + " p: " + getThreadState(((KThread) threadList.get(counter))).getEffectivePriority());	   
		    return getThreadState((KThread) threadList.get(counter));

	    }
    }


    protected class ThreadState2 extends PriorityScheduler.ThreadState{

    		public ThreadState2(KThread thread){
			super(thread);
		}		

	    /**
	     * Return the effective priority of the associated thread.
	     *
	     * @return	the effective priority of the associated thread.
	     */
	    public int getEffectivePriority() {
		    PriorityQueue waitQueue = null;
		    ArrayList threads = null;
		    int current = 0;

		    //Search through the threads from the waitingQueues that I own and 
		    //threads in queues that those threads own.
		    //If any of their priorities is higher than mine, then use the highest.
		    if (effectivePriority == recalcPriority){ //First check whether there was a possible priority chang
			effectivePriority = priority;
			    for (int i = 0; i < aquiredList.size(); i++){
				    waitQueue = (PriorityQueue) aquiredList.get(i);		
				    threads = waitQueue.getThreadList();
				    for (int j = 0; j < threads.size(); j++){
					    current = ((ThreadState)((KThread)threads.get(j)).schedulingState).getEffectivePriority();
					    if(current > 0){
					    	effectivePriority += current;
					    }
				    }
			    }	
		    }	    
	    
	    if (effectivePriority <= 0){
		    effectivePriority = getPriority();
	    }
	    return effectivePriority;
    }	    
}
}
